/*
 * @lc app=leetcode.cn id=874 lang=golang
 *
 * [874] 模拟行走机器人
 */

// 2. 抄题解的
// @lc code=start
func robotSim(commands []int, obstacles [][]int) int {

	// 初始化障碍点位
	obstacleMap := make(map[[2]int]bool)
	for _, obstacle := range obstacles {
		obstacleMap[[2]int{obstacle[0], obstacle[1]}] = true
	}

	// 当前方向
	dir := 0

	// 方向数组
	dx, dy := []int{0, 1, 0, -1}, []int{1, 0, -1, 0}

	// 当前位置
	x, y := 0, 0

	// 答案
	ans := 0

	for _, command := range commands {
		if command == -2 {
			dir = (dir + 3) % 4
			continue
		}

		if command == -1 {
			dir = (dir + 1) % 4
			continue
		}

		for i := 0; i < command; i++ {
			// 遇到障碍物
			if _, ok := obstacleMap[[2]int{x + dx[dir], y + dy[dir]}]; ok {
				break
			}
			x += dx[dir]
			y += dy[dir]

			ans = max(ans, x*x+y*y)
		}
	}

	return ans

}

func max(a int, b int) int {
	if a > b {
		return a
	}
	return b
}

// @lc code=end

// 1.
// n: 北
// s: 南
// e: 东
// w: 西
// @lc code=start
func robotSim(commands []int, obstacles [][]int) (ans int) {
	x, y := 0, 0

	xMap := make(map[int][]int)
	yMap := make(map[int][]int)

	for i := 0; i < len(obstacles); i++ {
		if _, ok := xMap[obstacles[i][0]]; ok { // 不能用 v = append(v, obstacles[i][1])
			xMap[obstacles[i][0]] = append(xMap[obstacles[i][0]], obstacles[i][1])
		} else {
			xMap[obstacles[i][0]] = []int{obstacles[i][1]}
		}
	}

	for i := 0; i < len(obstacles); i++ {
		if _, ok := yMap[obstacles[i][1]]; ok {
			yMap[obstacles[i][1]] = append(yMap[obstacles[i][1]], obstacles[i][0])
		} else {
			yMap[obstacles[i][1]] = []int{obstacles[i][0]}
		}
	}

	for _, v := range xMap {
		sort.Ints(v)
	}

	for _, v := range yMap {
		sort.Ints(v)
	}

	var recursion func(direction byte, i int)
	recursion = func(direction byte, i int) {
		if i == len(commands) {
			return
		}
		if commands[i] == -1 || commands[i] == -2 {
			recursion(turn(direction, commands[i]), i+1)
		} else {
			if direction == 'n' {
				temp := y + commands[i]
				if v, ok := xMap[x]; !ok {
					y = temp
				} else {
					for i := 0; i < len(v); i++ {
						if y < v[i] && v[i] <= temp {
							y = v[i] - 1
							break
						}

						if i == len(v)-1 {
							y = temp
						}
					}
				}

			} else if direction == 's' {
				temp := y - commands[i]
				if v, ok := xMap[x]; !ok {
					y = temp
				} else {
					for i := 0; i < len(v); i++ {
						if temp <= v[i] && v[i] < y {
							y = v[i] + 1
							break
						}
						if i == len(v)-1 {
							y = temp
						}
					}
				}
			} else if direction == 'e' {
				temp := x + commands[i]
				if v, ok := yMap[y]; !ok {
					x = temp
				} else {
					for i := 0; i < len(v); i++ {
						if x < v[i] && v[i] <= temp {
							x = v[i] - 1
							break
						}
						if i == len(v)-1 {
							x = temp
						}
					}
				}
			} else if direction == 'w' {
				temp := x - commands[i]
				if v, ok := yMap[y]; !ok {
					x = temp
				} else {
					for i := 0; i < len(v); i++ {
						if temp <= v[i] && v[i] < x {
							x = v[i] + 1
							break
						}
						if i == len(v)-1 {
							x = temp
						}
					}
				}
			}
			ans = max(ans, x*x+y*y)
			recursion(direction, i+1)
		}
	}
	recursion('n', 0)
	return
}

func turn(origin byte, command int) byte {
	if origin == 'n' {
		if command == -1 { // 右转
			return 'e'
		} else { // 右转
			return 'w'
		}
	}

	if origin == 's' {
		if command == -1 {
			return 'w'
		} else {
			return 'e'
		}
	}

	if origin == 'e' {
		if command == -1 {
			return 's'
		} else {
			return 'n'
		}
	}

	if origin == 'w' {
		if command == -1 {
			return 'n'
		} else {
			return 's'
		}
	}
	return origin
}

func max(x, y int) int {
	if x > y {
		return x
	}
	return y
}

// @lc code=end

